package practice1_100;

public class Practice516 {
    public int longestPalindromeSubseq(String s) {
        char[] chars=s.toCharArray();
        int[][] dpTable=new int[s.length()][s.length()];
        for (int i = 0; i < dpTable.length; i++) {
            dpTable[i][i]=1;
        }
        for (int i = 1; i < dpTable.length ; i++) {
            for (int j = i-1; j >=0; j--) {
                if(i==j+1){
                    if(chars[i]==chars[j]) dpTable[j][i]=2;
                    else   dpTable[j][i]=1;
                }else  {
                    if(chars[i]==chars[j])
                        dpTable[j][i]=dpTable[j+1][i-1]+2;
                    else dpTable[j][i]=Math.max(Math.max(dpTable[j+1][i-1],dpTable[j][i-1]),dpTable[j+1][i])  ;
                }
            }
        }
        return dpTable[0][dpTable.length-1];
    }

    public static void main(String[] args) {
       int a= new Practice516().longestPalindromeSubseq("bbbabhsabdbbdbsjgsgjldsjoeaaaaaahfjdwjvnskdkndaabbccddddddddd");
       //bbbabhsabdbbdbsjgsgjldsjoeaaaaaahfjdwjvnskdkndaabbccddddddddd
        System.out.println(a);
    }
}
